//已知一个由像素点组成的单色屏幕，每行均有 w 个像素点，所有像素点初始为 0，左上角位置为 (0,0)。 
//
// 现将每行的像素点按照「每 32 个像素点」为一组存放在一个 int 中，再依次存入长度为 length 的一维数组中。 
//
// 我们将在屏幕上绘制一条从点 (x1,y) 到点 (x2,y) 的直线（即像素点修改为 1），请返回绘制过后的数组。 
//
// 
//
// 注意： 
//
// 
// 用例保证屏幕宽度 w 可被 32 整除（即一个 int 不会分布在两行上） 
// 
//
// 
//
// 示例 1： 
//
// 
// 输入：length = 1, w = 32, x1 = 30, x2 = 31, y = 0
// 输出：[3]
// 解释：在第 0 行的第 30 位到第 31 位画一条直线，屏幕二进制形式表示为 [00000000000000000000000000000011]，因此
//返回 [3]
// 
//
// 示例 2： 
//
// 
// 输入：length = 3, w = 96, x1 = 0, x2 = 95, y = 0
// 输出：[-1, -1, -1]
// 解释：由于二进制 11111111111111111111111111111111 的 int 类型代表 -1，因此返回 [-1,-1,-1] 
//
// 
//
// 提示： 
//
// 
// 1 <= length <= 10^5 
// 1 <= w <= 3 * 10^5 
// 0 <= x1 <= x2 < w 
// 0 <= y <= 10 
// 
//
// Related Topics 位运算 数组 数学 👍 30 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-07-17 00:10:32
 * @description 面试题 05.08.绘制直线
 */
public class DrawLineLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 DrawLineLcci fun=new DrawLineLcci();
	 	 Solution solution = fun.new Solution();
		solution.drawLine(2,64,0,52,0);
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 // 一个单色屏幕的宽度不一定，但它总是 32 的倍数
	// 实际上是在一个二维数组中绘制一条水平线
	//每一行有w/32个整数，先定位到数组需要修改的行，然后修改对应的整数
	//比如 一行有 96个像素点，那么每行有3个整数,一共三行
	// 如果修改x1=30,x2=60，y=1
	//那么length=3*3=9,首先定位到y=1的行，那么起始位置是3*1=3，结束位置是3*1+3-1=5
	//然后修改序号3,4,5这三个整数
	// 第一个整数是0-1位，第二个整数是2-31位，
	// 如果横跨的整数不止一个，那么中间的整数全部置为-1，所以只需要修改第一个整数和最后一个整数
	//第一个整数是修改低位，最后一个整数是修改高位
    public int[] drawLine3(int length, int w, int x1, int x2, int y) {
		int[] screen = new int[length];
		int intsPerRow = w / 32; // 每行的整数个数
		int rowStart = y * intsPerRow; // 定位到第y行的起始位置
		int startIntIndex = rowStart + x1 / 32; // 起始整数的索引
		int endIntIndex = rowStart + x2 / 32; // 结束整数的索引
		int startBit = x1 % 32; // 起始位在整数中的位置
		int endBit = x2 % 32; // 结束位在整数中的位置
		if (startIntIndex == endIntIndex) {
			// 起始和结束在同一个整数内 1<x 再-1，会把x1到x2之间的位全部置为1
			int mask = ((1 << (endBit - startBit + 1)) - 1) << (31-endBit);
			screen[startIntIndex] |= mask;
		} else {
			// 处理起始整数
			int startMask;
			if (startBit == 0) {
				startMask = -1; // 所有位都为1
			} else {
				startMask = (1 << (32 - startBit))-1; // 从startBit到最高位置1
			}
			screen[startIntIndex] |= startMask;

			// 处理结束整数
			int endMask;
			if (endBit == 31) {
				endMask = -1; // 所有位都为1
			} else {
			    endMask = (-1 << (31 - endBit)); // 从第0位到endBit置1
			}
			screen[endIntIndex] |= endMask;
			// 中间的整数全部置为-1
			for (int i = startIntIndex + 1; i <endIntIndex; i++) {
				screen[i] = -1;
			}
		}
		return screen;
    }

	public int[] drawLine(int length, int w, int x1, int x2, int y) {
		int[] screen = new int[length];
		int intsPerRow = w / 32; // 每行的整数个数
		int rowStart = y * intsPerRow; // 定位到第y行的起始位置
		int startIntIndex = rowStart + x1 / 32; // 起始整数的索引
		int endIntIndex = rowStart + x2 / 32; // 结束整数的索引
		int startBit = x1 % 32; // 起始位在整数中的位置
		int endBit = x2 % 32; // 结束位在整数中的位置
		if (startIntIndex == endIntIndex) {
			// 起始和结束在同一个整数内 1<x 再-1，会把x1到x2之间的位全部置为1
			int mask = ((1 << (endBit - startBit + 1)) - 1) << (31-endBit);
			screen[startIntIndex] |= mask;
		} else {
			// 使用更安全的位运算方法
			screen[startIntIndex] |= (-1 >>> startBit); // 起始掩码
			screen[endIntIndex] |= (-1 << (31 - endBit)); // 结束掩码
			// 中间的整数全部置为-1
			for (int i = startIntIndex + 1; i <endIntIndex; i++) {
				screen[i] = -1;
			}
		}
		return screen;
	}

	public int[] drawLine1(int length, int w, int x1, int x2, int y) {
		int[] screen = new int[length];
		int intsPerRow = w / 32;
		int rowStart = y * intsPerRow;

		for (int x = x1; x <= x2; x++) {
			int arrayIndex = rowStart + x / 32; // 在screen数组中的索引
			int bitPosition = 31 - (x % 32); // 在整数中的位位置（假设最高位在最左）

			screen[arrayIndex] |= (1 << bitPosition);
		}

		return screen;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
